Twierdzenie Sprague’a-Grundy’ego

Twierdzenie Sprague’a-Grundy’ego – twierdzenie dotyczące gier, które są:

• bezstronne (impartial), czyli gracze mogą wykonywać dokładnie te same ruchy w danej sytuacji
• normalne (normal game), czyli przegrywa ten, kto nie może zrobić ruchu
• w każdej pozycji można wykonać skończoną liczbę ruchów
• każda rozgrywka ma skończoną długość

Funkcja Sprague’a-Grundy’ego:

jest określona rekurencyjnie

F(p)=0 dla pozycji p, dla której nie można wykonać ruchu

F(k)= mex(A) gdzie A, to zbiór wartości funkcji F dla pozycji, do których możemy dojść w jednym ruchu z pozycji k jeśli A nie jest pusty.

Twierdzenie Sprague’a-Grundy’ego:

Gracz ma strategię zwycięską wtedy i tylko wtedy, gdy wartość funkcji Sprague’a-Grundy’ego jest różna od 0. Wartość funkcji Sprague’a-Grundy’ego dla sumy gier (tzn. gra toczy się na kilku planszach, gracz w dowolnym ruchu wykonuje ruch na jednej planszy) wyraża się wzorem:

$F(P_{1},P_{2},\dots ,P_{n})=F(P_{1})\oplus F(P_{2})\oplus \ldots \oplus F(P_{n})$

gdzie suma nimliczb po prawej stronie równości oznacza operację xor na liczbach F(P1), F(P2), ...F(Pn)

Przykłady

1) gra nim: Jest n żetonów. Gracz wykonuje ruch biorąc jeden, dwa, trzy lub cztery żetony, gdy nie ma żetonów gracz przegrywa. F(n) funkcja Sprague’a-Grundy’ego dla tej gry wynosi (n oznacza liczbę żetonów)

F(0) = 0

F(1) = 1 (gdy na planszy jest jeden żeton, to jedynym ruchem jest wzięcie tego żetonu, wtedy F wyniesie 0 zatem najmniejszą nieosiągalną wartością jest 1)

F(2) = 2 (osiągalne są 0 i 1, najmniejszą nieosiągalną jest 2)

F(3) = 3 (osiągalne są 0, 1 i 2, najmniejszą nieosiągalną jest 3)

F(4) = 4 (osiągalne są 0, 1, 2 i 3, najmniejszą nieosiągalną jest 4)

F(5) = 0 (osiągalne są 1, 2, 3 i 4, najmniejszą nieosiągalną jest 0)

F(5k) = 0

F(5k+1) = 1

F(5k+2) = 2

F(5k+3) = 3

F(5k+4) = 4

Czyli gracz ma strategię wygrywającą wtedy i tylko wtedy, gdy na planszy jest liczba żetonów niepodzielna przez 5. Jego ruchem jest zabrać tyle żetonów, by pozostała liczba podzielna przez 5.

2) multinim: Są trzy plansze z odpowiednio n, m, k żetonami. Gracz w pojedynczym ruchu zabiera z jednej planszy 1,2,3 lub 4 żetony. Funkcja Sprague’a-Grundy’ego dla tej gry wynosi P(n,m,k) = F(n) xor F(m) xor F(k) (F – funkcja z poprzedniego przykładu).

Jeśli na planszach jest odpowiednio: 16, 17 i 18 żetonów, to funkcja P(16,17,18) = F(16) xor F(17) xor F(18) = 1 xor 2 xor 3 = 0. Czyli pierwszy gracz nie ma strategii zwycięskiej.

Jeśli na planszach jest odpowiednio: 17, 18 i 19 żetonów, to funkcja P(17,18,19) = F(17) xor F(18) xor F(19) = 2 xor 3 xor 4 = 5. Pierwszy gracz ma strategię zwycięską. By zwyciężyć powinien zabrać trzy żetony z trzeciej planszy.

Twierdzenie sformułowali niezależnie od siebie R.P. Sprague (1935) oraz P.M. Grundy (1939).

Bibliografia

• Thomas S. Ferguson, Game Teory.